# 24. 常用算法题思路

# 1. 递归（Recursion）—— "自己叫自己"

就是函数里调用函数本身，像套娃一样。

通俗说：你要数一盒子里有多少层套娃。你打开一个，发现里面还有一个，就继续打开，直到打开最后一个。

代码像这样：

function count(n) {
    if (n === 1) return 1;  // 最小的那个
    return 1 + count(n - 1); // 自己调用自己
}

1
2
3
4

特点：思路简单，但容易"爆栈"（递归太深会内存溢出）。

# 2. 回溯（Backtracking）—— "走不通就退回来换条路"

递归 + 撤销操作 = 回溯。试错法，不行就回头。

通俗说：你在迷宫里走，走到死胡同就退回来，在岔路口换另一条路继续走。走一步记一步，走不通就擦掉脚印退回上一步。

经典场景：八皇后问题、全排列、解数独。

// 伪代码思路
function backtrack(路径) {
    if (满足条件) return 结果;
    for (选择 in 所有选择) {
        做选择;           // 往前走一步
        backtrack(路径);   // 继续走
        撤销选择;          // 走不通，退回来
    }
}

1
2
3
4
5
6
7
8
9

特点：暴力枚举所有可能，但会"剪枝"（提前排除明显不行的路）。

# 3. DFS（深度优先搜索）—— "一条道走到黑"

和回溯是"亲兄弟"，本质都是递归，但 DFS 更注重"遍历所有节点"。

通俗说：你进了一个迷宫，一直靠右走，不撞南墙不回头，走到头再退回来换路。

两者区别：

DFS 侧重"遍历"整个图/树，把所有节点都访问一遍。
回溯侧重"找解"，找到了可能就停了，而且会撤销操作。

例子：遍历文件夹所有文件，就是 DFS。

# 4. BFS（广度优先搜索）—— "一层一层往外扩"

像水波一样，从起点一圈一圈往外扩散。

通俗说：你站在商场中央，先问离你最近的店员，再问稍微远一点的，再问更远的。先近后远，层层推进。

实现方式：用队列（先进先出）。

// BFS模板
function bfs(起点) {
    let queue = [起点];
    while (queue.length) {
        let node = queue.shift(); // 取出队首
        // 处理当前节点
        for (let neighbor of node.邻居) {
            queue.push(neighbor); // 邻居入队
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11

特点：能找到最短路径（因为是一层层扩的），但比较耗内存。

# 5. 贪心（Greedy）—— "每次都选当下最好的"

目光短浅，只看眼前利益，不回头看。

通俗说：你饿了，面前有一堆大小不一的包子。每次都拿最大的那个，不管后面还有没有更大的。

经典场景：找零钱（用最少张纸币）、活动安排问题。

// 贪心思路
function greedy(问题) {
    while (还有选择) {
        选当前看起来最优的那个;
    }
}

1
2
3
4
5
6

特点：快！但不一定对，需要证明"局部最优 = 全局最优"才行。

# 6. 动态规划（DP）—— "记住之前算过的，避免重复劳动"

把大问题拆成小问题，记住小问题的答案，后面直接用。

通俗说：你要爬 10 层楼，每次可以爬 1 层或 2 层。你想知道有多少种爬法。

不用 DP：你会重复算"爬第 5 层有多少种方法"很多次。
用 DP：你拿个本子，算完第 1 层、第 2 层……都记下来，算第 5 层时直接查本子。

核心三要素：

DP 状态：本子上记的是什么？（比如 dp[i] = 爬到第 i 层有几种方法）
状态转移方程：怎么从前面推后面？（dp[i] = dp[i-1] + dp[i-2]）
初始条件：本子第一页怎么写？（dp[1] = 1, dp[2] = 2）

# 7. DP状态（DP State）—— "本子上记的那句话"

就是你在本子上记的"什么是什么"。

通俗说：你记账本，每一行写的是"日期 + 花了多少钱"。这里的"日期 + 金额"就是状态。

常见状态：

dp[i]：前 i 个元素的最优解
dp[i][j]：从 i 到 j 的最优解
dp[i][j]：背包容量 i，前 j 个物品的最大价值

关键：状态定义得好，转移方程就自然出来了。

# 📊 总结对比表（一眼看懂）

算法	一句话概括	核心工具	适用场景
递归	自己调用自己	函数栈	问题可以拆成同类型的子问题
回溯	走不通就退回来换路	递归 + 撤销	全排列、组合、棋盘问题
DFS	一条道走到黑	递归/栈	遍历树/图
BFS	一圈一圈往外扩	队列	最短路径、层次遍历
贪心	每次都选当下最好的	排序/堆	局部最优=全局最优的问题
DP	记住之前的答案	数组/哈希表	最优子结构、重叠子问题
DP状态	本子上记的"什么是什么"	变量定义	DP 问题的第一步

# 🎯 它们之间的关系（重点）

递归 = 一种写法（自己调自己）
  ├── 回溯 = 递归 + 撤销操作（找解）
  └── DFS = 递归遍历（遍历所有节点）

BFS = 用队列遍历（和DFS是"兄弟"，都是遍历方法）

贪心 = 每步选最优（不用递归，直接循环）

DP = 递归 + 备忘录（记住算过的值，避免重复）
      = 把递归从"顶向下"改成"底向上"的填表法

1
2
3
4
5
6
7
8
9
10

# 💡 再举个具体例子区分

问题：从起点走到终点，找一条路径。

DFS：不管远近，先沿着一条路走到黑，到了终点就返回（不管是不是最短）。
BFS：一层一层找，第一次到终点时一定是最短路径。
回溯：和 DFS 一样走，但到了终点会记录路径，然后退回继续找所有路径。
贪心：每步都选看起来离终点最近的方向，不管后面有没有障碍。
DP：记录每个点到终点的最短距离，后面直接用。

← 23. 性能优化方法 1. vue中的watch和data用法 →